Most sources claim Robert Altmans *M*A*S*H* contained the first 'Fuck' in a major motion picture, it was already the first for other things (first use of sound bridging!) so it's happy to push boundaries. It was actually only the first Hollywood film to do so.
That being said, the climax of The Graduate (1967) features a scene in which Ben Braddock can be seen (but not heard) shouting "What the fuck are you doing?" to Elaine as she stands at the alter, as he is behind glass.
However, both Ulysses and I'll Never Forget What's'isname used it beforehand, both also being released in 1967. Ulysses however, was released in June of that year as opposed to the December opening of I'll Never Forget What's'isname, making Ulysses the winner.
1967 was a good 'fucking' year.
Others have argued over the first 'profanity' spoken in a movie, with Hell's Angels being the most likely candidate (considering the amount of times 'damn' and 'son-of-a-bitch' is apparently uttered during dogfight sequences.