My great Grandfather was born in Istebna in the 1880's and my wife's great grand parents were both born in Warsaw in the 1880's. All name's were changed when they immigrated to (mine) was the US, my wife's immigrated to Canada and later the US. My question is, is there a way to find their names prior to immigration? And possibly family history.
The geneteka website is amazing. (Polish) Rather than try to explain it just take a couple hours to look at it. They have over 30 million church records indexed in a computer searchable database. I found it on Cyndislist but you can probably just search for geneteka. I stumbled around and found lots of stuff so you can as well.
Don't be surprised how many hits you get even if the name sounds unusual to you. If you know his parents they will likely be in the birth records and I think even marriage records. That's how I found my dziadek. I had his parents names on his marriage license (US) so I could tell when I found the right Stanisław's birth record in Poland.
If you don't know his parents, consider looking for his naturalization records. That record lists all kinds of great info, including parents, hometown, ship he came over on. Read about the history of how immigrants became naturalized citizens for specifics. Before 1912(+/-) Naturalization was handled at the local courthouse. Some of the spelling might be a little more "creative" than you'd like. But before you send the feds their $65 fee, check with the records people in the town where he settled. They had the record for my dziadek and sent me a copy for free in less than a week. I just consider the $65 I sent the feds and the 6 weeks I waited for a "sorry" letter as an expensive lesson.
Good luck. It is quite frustrating until you hit paydirt. Then it is kind of a hoot.