It certainly depends on what kind of interactions you're looking for.
As has been already mentioned, there are options for prediction by protein docking. You can use ZDOCK online (http://zdock.umassmed.edu/) but even that software is limited by the availability of protein structures. I also found the PRISM server (http://cosbi.ku.edu.tr/prism/) recently but haven't tried it yet.
Sometimes it's easiest just to check on proteins in the STRING database first (http://string-db.org/) - most of its interactions are really just predictions. I'm also familiar with iLoops (http://sbi.imim.es/iLoopsServer/). It doesn't require a structure but just makes feature-based predictions.
A number of tool servers unfortunately only do predictions for common model organisms (i.e., yeast) so hopefully that doesn't matter for you.