In his first consulship he was the senior consul, and his colleague was Publius Valerius Poplicola.
Nautius was given command of Roman forces against the Volsci who had invaded Latium.
Nautius held the consulship a second time in 458 BC with Lucius Minucius Esquilinus Augurinus.
That same year, the Aequi attacked the allied city of Tusculum and defeated his colleague, Minucius.
Nautius Rutilus returned to Rome to oversee the Roman Senate electing a dictator, Lucius Quinctius Cincinnatus, to deal with the invaders.