Credit check to open a checking account
Did you walk in with a deposit to open the account with? Admittedly it has been a while since I opened a new account, but that is all that was required.
But that was at a Credit Union that I had just become eligible to join, so I would also look for a credit union, and they will save you money vs. a for profit bank.