Paul Marcus Cleary (born 28 April 1976 in Melbourne, Victoria) is a retired male middle-distance runner from Australia, who represented his native country at the 1996 Summer Olympics in Atlanta, Georgia. There he was eliminated in the qualifying heats of the men's 1,500 metres competition. He set his personal best (3.36.20) in the men's 1500 metres on 13 March 1999 in Brisbane, Australia.