Gaius Nautius Rutilus was consul of the Roman Republic in 475 BC and 458 BC.

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 ravaged the Volscian territory, but there was no significant engagement with the enemy.

Nautius held the consulship a second time in 458 BC with Lucius Minucius Esquilinus Augurinus. During his second consulship, he successfully carried on war against the Sabines. 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.

Nautius was probably the brother, or perhaps the son of Spurius Nautius Rutilus, consul in 488 BC.