The problem that occurs in the cleaning service staff at PT KAI is that besides cleaning the station area, they also have to do other work, such as cleaning trains, filling water in train toilets which should have its own officers. There are still many train passengers who dispose of their waste improperly, thereby increasing the workload of cleaning service officers. Another problem is the lack of division of tasks in each element of work. The number of officers in each shift is also not the same, a minimum of 2 and a maximum of 8 people. The number of officers on the morning and evening shifts is 6 to 8 people, while the night shift is 2 to 3 people. The cleaning service staff works for 8 hours per shift with no break time, resulting in complaints of fatigue of the cleaning service staff. This study aims to analyze the physical and mental workload on the cleaning service staff at PT. KAI Daop VI Yogyakarta using work sampling and NASA-TLX methods. Based on the results of this study it was known that the physical workload of staff on the morning shift was 88.6% (=7.1 hours) and on shift 1 it was 93% (=7.4 hours) for 8 productive working hours. The mental workload of staff on shift 1 was 73.3% and 75.0% on shift 2. This indicated that the cleaning service staff workload was classified as heavy and there was a need to improve the work system. This condition indicates that the cleaning service staff workload is heavy and needs to improve the work system.