use an Index correctly to optimize queries

I have an sql database with millions of records and when i'm querying the data like

`select * from ActCosts where ScenarioID= 456`

it gives me like 50,000+ rows which is surprisingly taking more than 3 minutes. So i am now thinking of how could i improve this performance. I find one way is to create an index on the column "SomeID" to optimize it.I do have created an index but the query takes the same time