There are three types of contacts in Podio: Podio connections, Workspace contacts, and contacts that are kept in a Contact App. Each type of contact is very different in its function, so it is important to understand the difference between them.
Please note: Workspace Contacts are disabled for any organizations created after November 24, 2016. We recommend that you use a Contact App to manage your contacts instead.
Podio connections
Podio connections are available via the contact icon in the top blue bar. 
These are all of your connections in Podio - other Podio members whom you share at least one workspace with. This means all of your colleagues and external members that you collaborate with will be automatically added to your Podio connections.
You'll notice that when you try to add a connection from here, you are prompted to add that person to one of your workspaces first. A person can only be added to your Podio connections when they are added to a workspace where you are also a member.
Similar to this, a connection can only be removed from your Podio connections when you no longer share a workspace with them. So, if someone has been removed from all of your workspaces and you no longer wish to see them in your Podio connections, you can go to your contacts page and select "Actions" next to their name, then "Remove connection". 
Contact apps
You can create a contact app to create a universal database for your contacts. This allows you to store all of your contacts in one place, where they can easily be referenced anywhere else in your organization. You can also import all of your existing contacts into this app.
We have a guide to setting up a Contact app here.
Workspace contacts
Please note: Workspace contacts are not available for organizations created after November 24, 2016.
Workspace contacts, not to be confused with workspace members, can be thought of as virtual business cards. They are not linked to existing Podio users, and they exist purely as contact information for you to reference.
Every workspace has a contacts section. To get there, click the wrench icon just above the workspace activity stream, then select "Workspace contacts".
From here you can see all of the contacts that you and your colleagues have added to the workspace. Contacts are added either from this workspace contacts page, or via a contact field in one of the apps in the workspace.
Workspace contacts can be referenced from any contact field that is set to tag workspace contacts. For example, if you have a Clients app, a contact field in this app will allow you to add the client's contact record to their item in your app. Note that you can also add new contacts from the contact field, so you can add contacts on the fly without having to navigate to the workspace contacts page.