Three species belonging to three genera of early Cenozoic nautilid cephalopods are described from Paleocene aged beds of the Pebble Point and Dilwyn formations, Victoria, Australia: Aturoidea distans Teichert, Eutrephoceras victorianum Teichert, both previously known from these deposits, and Nautilus praepompilius Shimansky, previously unknown from Australia. Here we present new occurrence and paleoecological information about these three taxa based on previously and newly collected specimens from Pebble Point Formation beds, as well as presenting the first paleotemperature analyses for Australian nautiloid cephalopods of any age. We sampled for shell carbonates from the single known specimen of Nautilus praepompililus, as well as from a specimen of Aturoidea distans from the Pebble Point beds. The A. distans samples showed temperature of calcification to have been between 20 and 25°C; and for N. praepompilius the temperatures were between 18 and 21°C. There were too few samples to provide statistical analyses, yet the implication is that these two taxa inhabited different depths during calcification. For comparison, we have sampled shell carbonates from the only known extant site where two different nautilid genera coexist, Manus Island, Papua New Guinea. There, specimens of Nautilus pompilius and Allonautilus scrobiculatus calcified (1984 specimens) at temperatures of 12 to 17°C, conforming to previous measurements in the literature and significantly colder than any of the Paleocene specimens sampled here.