The California Gull (Larus californicus) has been expanding its breeding range southward in the western United States, including in the Rocky Mountains, for several decades. In New Mexico, the species was accidental in occurrence until numbers appeared in summer in the mid-1970s. Here we document the first breeding of the California Gull in New Mexico, where a small colony containing four broods was discovered in 2013; this event extends the known breeding range southward in the Rocky Mountains by about 150 km. Nesting will likely continue at least intermittently in New Mexico as water levels in the state’s reservoirs, and the presence of islands suitable for nesting, fluctuate over time.