To block Skype, Skype-probe needs to be allowed. Skype-probe runs over port 80 and is sets up initial connections. When Skype-probe is blocked, the application encrypts the communication and starts alternate open ports, which is why it needs to be allowed.
Steps
The following procedure blocks Skype traffic on the Palo Alto Networks firewall:
From the Web UI, go to Policies > Security and click the Add icon in the lower left:
Select Application tab and set the application to "Skype-probe." The source should be any applicable internal zones.
Set destination to any.
Set action to allow.
Create a similar second rule but with the following changes: