Summary: This paper studies the problem of orthogonal packing rectangles in a circle (OPRC), which requires finding a subset of rectangles that can be packed into a circular container to maximize the area or the number of packed items. The skyline is widely used for the rectangle packing problem (RPP) due to its simplicity and efficiency in checking the feasibility and evaluation of placement. Several skyline-based best-fit heuristics have been introduced and obtained the best results for the RPP. The only difference between the OPRC and RPP is that the container in RPP is a rectangle, while that in OPRC is a circle. It is still an open question whether the skyline could be used to solve the OPRC. The initialization, skyline update method, and fitness function must be carefully designed due to the circle boundary. This paper adapts the skyline for the first time to solve the OPRC. It proposes a skyline-based heuristic consisting of a greedy approach to generate the initial skyline, several rules to update the skyline, and a best-fit function to select and pack the rectangle iteratively according to a given sequence of rectangles. Then, it employs the variable neighborhood search algorithm consisting of two shaking and three local search operators to improve the solution. The benchmark instances’ results show the proposed approach’s effectiveness and efficiency, improving the best-known solutions for most (24 out of 27 for maximizing area and 25 out of 27 for maximizing the number) large-scale instances within less computing time.