creating a primary key on table with data in it

You don't necessarily need a primary key (although one wonders how you uniquely identify the data in your table without having one) but instead an index. Probably you need a clustered index. Use the CREATE INDEX syntax to make one using the column (or columns) that is most commonly used to retrieve your data. http://msdn.microsoft.com/en-us/library/ms188783.aspx

Having an index on this table wont speed up the time to get the data when you select all the data. Whether it is an index or a table, all the data is all the data and that needs to be read from the disk and passed to your client. If your query however selects only a few columns from the table and then filters out a lot of rows with a WHERE clause then indexing will help.

When you tried to create the primary key did you expect the columns to be unique in their values? Do you think you have a data integrity issue?

As Grant says, you can still create a clustered index on your table that will significantly improve query times - so long as you are filtering out rows and not requesting every column.