Protein interactions, key to many biological processes, involves induced fit between flexible proteins which typically undergo conformational changes. Modeling this flexible protein-protein docking is an important step in drug discovery, structure determination and understanding structure-function relationships. In this paper, we present F³Dock, a Fast Flexible and Fourier based docking algorithm which utilizes adaptive sampling of orientation and conformational spaces, and a hierarchical molecular flexibility and structure representation. Different conformations are adaptively sampled and docked using a Non-equispaced Fast Fourier based algorithm.