We demonstrate passive mode locking based on the novel monoclinic double tungstate crystal Yb:KLu(WO4)2. We report the shortest pulses ever produced with an Yb-doped tungstate laser using a semiconductor saturable absorber. A pulse duration of 81 fs has been achieved for an average power of 70 mW at 1046 nm. We compare the performance of the polarization oriented parallel to the Nm- and Np-crystallo-optic axes. Results in the femtosecond and picosecond regime are presented applying either Ti:sapphire or diode laser pumping. The great potential of Yb:KLu(WO4)2 as an active medium for ultrashort pulses is demonstrated for the first time, to our knowledge.