We provide an algorithm to construct a multicomplex for any lower Bruhat interval of $F_4$, such that its rank--generating function equals that of the Bruhat interval. For Weyl groups, it is always possible to find such a multicomplex thanks to the work of Björner and Ekedahl. The algorithm is based on only two functions, which weaken the notion of Lehmer code for finite Coxeter groups, motivated by the fact that a strong Lehmer code for type $F_4$ does not exist. We also realize the set of palindromic Poincaré polynomials of $F_4$ as an induced subposet of the Bruhat order that forms a lattice.