There are many factors that determine the "success" - be it to preserve the original board and pads, or to preserve the chip itself. Generally (not always but usually) boards with BGA devices are multilayer and will most likely have a few power/ground planes - that will sink heat away from the site meaning it takes longer to heat up that area - and the longer you heat the board, the further the heat spreads and the greater the potential for board damage.
I have successfully removed BGA devices with a simple temperature controlled hot air station (cheap 898D) but it needed the board to be preheated to reduce the temperature difference. But that is just the first part. Even if you don't plan on soldering a new chip to the board - if you don't want shorts between the remaining pads they will need at least some clean up. Doesn't have to be perfect, but, again, due to the ground planes, it can be hard to get any remaining solder to melt. For that I would advise a reasonably powerful iron, > 65W with a large tip + solder wick and plenty of flux. You would to gently lay the solder wick over the pads and let the iron heat it up. Do not press down with any force or drag the iron/wick from side to side with any force. Let it melt the solder and "ride" on top of the pads/flux - otherwise you could just swipe pads right off (if you don't plan on using the pads again, this may not be a problem, but still looks awful).
So yes, you need flux, plenty of it. And given its a BGA you want liquid or tacky - putting a line of it along each edge of the chip means that once you start heating, it'll liquify, and flood under the chip.
As for temperature, I never go above 360C, but... it all depends on the nozzle width, width of chip, how far away from the chip you're at etc.. there isn't a particular "this distance, at this temp, for this time".
Sure, higher temperature, means it heats up the board quicker - but it also raises the maximum temp the board can get to, and it should never get to 400C...
Best advice I can give if you value the board you're working on - find some scrap boards, and practice. And keep going until you can lift a chip fairly quickly without any signs of bubbling/warping or heaven forbid, scorching on the board. Smaller PCB's are easier as they have less thermal mass, but something like a modern graphics card will most certainly require preheating, or it will take ages and permenantly damage the board.
How big of a chip are we talking? a 5x5mm? or something beastly like BGA289? And a photo of the board will help