Moving the data into another table would still require indexes: one on the original table's column (which now stores the new id) and one on the new table's primary key.

In most cases I'd expect just adding an index to the original table to be more efficient, but it depends on the type of the original column and if some data could be de-duplicated by the normalization.