Strategic allocation of male mating effort is expected if females vary greatly in reproductive value and/or the costs of mating for males are high. Here, we conducted experiments investigating male signalling effort in the Australian desert goby, Chlamydogobius eremius. Males in this species exhibit elaborate courtship of females and exclusive parental care. In the first experiment, we offered focal males two females presented simultaneously in a dichotomous choice design. We found that males preferentially courted the larger of the two females. We found that the same was also true when, in a second experiment, males were presented with females sequentially. Intriguingly, the order of presentation appeared to be important, with males adjusting their courtship depending on the size of the female encountered previously. Our study highlights male mate choice as an important source of variation in male signalling effort.