Several studies have been conducted with the purpose of searching materials which will modify bitumen resulting with good performance characteristics and permanent deformation resistance. In Ethiopia while one of the major pavement distresses is rutting, there is no significant effort to minimize distress by using modified binder of improved visco-elastic property, more over the binder grading system is not performance based. Therefore, the main objective of this study is to evaluate rheological characteristics and the performance of bitumen at high temperature in rut resistance when bitumen is modified with crushed cattle bone (CCB). Bone is an abundant waste material and contains inorganic materials which give its strength. Using this modifier laboratory produced samples were 3, 6 and 9% CCB by weight of the bitumen were prepared. The control material was 60/70 penetration grade neat bitumen. To evaluate the visco-elastic properties of these modified samples different Dynamic Shear Rheometer (DSR) tests were carried out. The major DSR tests were Amplitude Sweep Test (AST), Frequency Sweep Test (FST), and Multiple Stress Creep Recovery (MSCR). Also Performance Grade (PG) determinations at high temperatures were conducted. From the AST results linear visco-elastic range was found to be 0.16%, which the test was conducted at 10°C, 21.1°C, 37.8°C, and 54.4 °C temperatures. Master curve was constructed using the data obtained from FST results at the same temperature as AST. Master curve showed that 6% and 9% addition of CCB on asphalt binder increases the stiffening property of asphalt binder at high temperatures and low loading frequencies (susceptible for rutting). The performance grade determination also depicted PG improvement from PG64-yy to PG70-yy with the addition of 9% CCB. Even though the non-recoverable creep compliance improves with the addition of 6% and 9% CCB, it is found that CCB replacement was not convenient in its percent recovery. In conclusion, 9% CCB modified binder is better in its rutting performance with improved performance grade.