Went to valley of fire yesterday for a quick trip an wow I could not believe how packed the place was. Had to wait in line for 20 min with a huge line of cars. All the lots were packed full 98% was California. And the campgrounds was all full. Did scout some nice camp spots for next time.
VoF is usually very crowded in the winter and early Spring. There are quite a few places to camp outside VoF in Lake Mead Recreation Area. Not sure about the western side of VoF as I don't know where the Reservation starts and if you can camp on Reservation lands.