Sure, you can start with frozen fish. Thaw your frozen fish by rinsing it in a colander under cold water (hot water would cook the fish), or in the refrigerator overnight.