Formé à l'Inter Milan, Paolo Orlandoni voyage au cours de sa carrière à travers de nombreux clubs. Il joue surtout en Serie B et C jusqu'en 2000 où il rejoint la Reggina, qui joue en Serie A.
Cependant, même s'il parvient enfin à jouer dans l'élite, il a du mal à s'imposer en tant que titulaire. Il joue ensuite les doublures à la Lazio de Rome et à Bologne avant de revenir dans son club formateur, l'Inter Milan où il occupe depuis 2006 la place de troisième gardien.
En il fête sa première sélection avec l'équipe d'Italie mais il n'a finalement pas été retenu pour participer à la coupe du monde.
Après avoir conquis de nombreux titres avec l'Inter (mais en tant que simple "remplaçant"), Paolo Orlandoni prolonge son contrat jusqu'au . Puis il prolonge d'une année supplémentaire, il est lié au club jusqu'au . Paolo Orlandoni tirera sa révérence à la fin de la saison 2012. Il occupera des fonctions au sein de son club formateur de l'Inter Milan, il sera entraîneur des gardiens dans la section jeune du club.
Palmarès
Vainqueur de la Coupe UEFA 1991 (Inter)
Champion de Série C en 1993 (Leffe)
Champion d'Italie en 2006, 2007, 2008, 2009 et 2010 (Inter)